package com.algorithm.quick;/*
 *@Author:DOWN
 *@Date:2022/1/20 15:09
 *@Comment:给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
           请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
           示例 1:
           输入: [3,2,1,5,6,4] 和 k = 2
           输出: 5

           示例 2:
           输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
           输出: 4
 */

import java.util.Arrays;
import java.util.Random;

public class Solution215 {
    private static Random random = new Random();
    private static int result;

    public static int findKthLargest(int[] nums, int k) {
        sortTwoWays(nums, 0, nums.length - 1, k,0);
        return result;
    }

    public static void sortTwoWays(int[] arrs, int l, int r, int k,int denth) {
        int changeIndex = l + (random).nextInt(r - l + 1);
        swap(arrs, l, changeIndex);
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arrs[i] < arrs[l]) {
                i++;
            }
            while (j >= i && arrs[j] > arrs[l]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arrs, i, j);
            i++;
            j--;
        }
        swap(arrs, l, j);
        if(j+k==arrs.length){
            result=arrs[j];
        }else if(j+k<arrs.length){
            //[j+1,arrs.length]
            sortTwoWays(arrs, j+1, r, k,denth+1);
        }else {
            //[0,j-1]
            sortTwoWays(arrs, l, j-1, k,denth+1);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    public static void main(String[] args){
        int[] ints={-1,-1};
        System.out.println(findKthLargest(ints,2));
        System.out.println(Arrays.toString(ints));
    }
}
